/**
 * 杨辉三角
 *
 * 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
 * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
 *
 * 示例 1:
 * 输入: numRows = 5
 * 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
 *
 * 示例 2:
 * 输入: numRows = 1
 * 输出: [[1]]
 *
 * 提示:
 * 1 <= numRows <= 30
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 正常的遍历用上面的数相加得到想下面的数就可以了
 * 时间复杂度 : O(n ^ 2)
 * 空间复杂度 : O(n ^ 2)
 */

public class Main {
    public List<List<Integer>> generate(int numRows) {

        List<List<Integer>> lists  = new ArrayList<>();

        for (int i = 0; i < numRows; i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j <= i; j++) {

                // 注意第一个数和最后一个数都为 1
                if (j == 0 || j == i) {
                    list.add(1);
                } else {
                    int m = lists.get(i - 1).get(j - 1);
                    int n = lists.get(i - 1).get(j);
                    list.add(m + n);
                }
            }
            lists.add(list);
        }

        return lists;
    }
}